package com.hdu.other.dp.maxSubArraySum;

public class lc213 {
    class Solution {
        public int rob(int[] nums) {
            int len = nums.length;
            if (len == 1)
            {
                return nums[0];
            }
            if (len == 2)
            {
                return Math.max(nums[0], nums[1]);
            }
            return Math.max(
                    subRob(nums, 0, len - 2),
                    subRob(nums, 1, len - 1)
            );
        }

        int subRob(int[] nums, int l, int r)
        {
            int len = r - l + 1;
            if (len == 1)
            {
                return nums[l];
            }
            if (len == 2)
            {
                return Math.max(nums[l], nums[l + 1]);
            }
            int a = nums[l];
            int b = Math.max(nums[l], nums[l + 1]);
            for (int i = l + 2; i <= r; i++)
            {
                int cur = Math.max(a + nums[i], b);
                a = b;
                b = cur;
            }
            return b;
        }
    }
}
